HW#1 --- last modified February 07 2019 23:07:54..

Solution set.

Due date: 1_DATE

Files to be submitted:
  Hw2.zip

Purpose: To reason about the hill-climbing, simulated annealing, and genetic algorithms. To code the minimax algorithm with alpha-beta pruning in a specific context.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO6 -- Students should be able to explain the advantages and disadvantages of hill climbing.

LO8 -- Students should be able to explain the advantages and disadvantages of alpha-beta pruning

Specification:

This homework consists of a book component and a coding component. Files for both components should be submitted in your Hw2.zip file along with a readme.txt with any additional instructions, a list of your team mates and their IDs. For the book portion of the homework I want you to do Problems 4.1 and 4.2 in the book. Write up your solutions in problems.txt, a plain text file. For students who are in CS286-2, I want you to in addition find the paper of the master student who first solved the game Connect-4. I want you to write a two page book report summarize his paper. I would also like you to do search on the current status of whether Checkers is solved or not and whether Chinese Checkers is solved or not. By solved, I mean that is known for a game like Connect-4 that the first person wins even if the second plays optimally.

For the coding part of the homework, I want you to write program to play dots-and-boxes on 4x4 grids of dots. Each dot in this grid is a number between 0 (top left) and 15 (lower right). Each box in the game is numbered from 0 to 8, where 0 is the box in the top left and 8 is the box in the lower right. The shell for your program should be in a game.py file. It will be run from the command line with a line like:

python game.py player_type1 player_type2

Here player_type_i can be either HumanPlayer or RobotPlayer. game.py should instantiate the two players. player_type1 plays x and goes first, player_type2 plays o. Then game.py should have the play a game of dots-and-boxes against each other. You should write an abstract class Player whose constructor takes either "x" or "o" as a string and saves this into a field variable. We refer to "x" and "o" as "player strings". For other inputs to the constructor it should raise a RuntimeError. In addition to the constructor, Player has an abstract method turn(board) which when implemented by a subclass takes as input a board is supposed to return a new board which results from the Player making a move. A board is a tuple whose first element is a list of the edges (represented as tuples) which have been chosen so far, and whose second component is a list of tuples of (player string, box numbers) for each of the boxes that have been filled in so far. For example, the board:

*-* * *
|o| |
*-* * *

* * * *

* * * *

would be represented as the tuple:

( [(0,1), (0,4), (1,5), (2,6), (4,5)], [("o", 0)])

For this homework, you should write two concrete subclasses for Player: HumanPlayer and RobotPlayer. When turn(board) is called on a HumanPlayer, it should pretty print the board to standard out and get a move from the player written in the tuple format above for boards; it should verify the move is legitimate, or else ask for a new move; if the move is legitimate, it should return that move. For a RobotPlayer, the turn(board) should compute a next board using minimax with alpha-beta pruning and a heuristic function of your choice. In the keyboard input for HumanPlayer tabs and spaces should be ignored. Recall if a player in dots-and-boxes makes a box they are allowed to choose another edge and they can repeat this until they can no longer make a box. The board returned by RobotPlayer in such an instance should be after the complete sequence of edge selections and box making has been applied. Three bonus points will be awarded for the best dots-and-box player in a mini tournament that I hold, 2 points for second best, 1 point for third place.

Point Breakdown